#include "dlinklist.h"

void rearrange(dlist head)
{
    dlist k=head->prev;

    // 从后到头遍历
    for(dlist p=head->prev; p!=head; p=p->prev)
    {
        // 1. 遇到奇数，记下当前的位置
        if(p->data%2 != 0)
            k = p;

        // 2. 遇到偶数，将其移动到末尾，然后直接跳到上一个奇数
        else
        {
            move_tail(head, p);
            p = k;
        }
    }
}

int main(int argc, char const *argv[])
{
    // 将若干自然数形成双循环链表
    int n;
    scanf("%d", &n);
    dlist head = init_list();
    for(int i=1; i<=n; i++)
    {
        dlist new = new_node(i);
        add_list_tail(head, new);
    }
    show(head);

    // 奇偶数重排
    rearrange(head);
    show(head);

    return 0;
}
